export class Node {
    constructor(element) {
        this.element = element
        this.next = null
    }
}

export class LinkedList {
    constructor() {
        this.head = null
        this.length = 0
    }
    // 尾部追加一项
    append(element) {
        const newNode = new Node(element)
        // 1.链表为空
        if (!this.head) {
            this.head = newNode
        } else {
            // 2.链表不为空
            let current = this.head
            while (current.next) {
                current = current.next
            }
            current.next = newNode
        }
        this.length++
    }
    // 在特定位置插入一个新的项
    insert(position, element) {
        // 0. 判断越界
        if (position < 0 || position > this.length) {
            return false
        }
        // 1. 插入 position = 0 的位置
        const newNode = new Node(element)
        if (position === 0) {
            newNode.next = head
            this.head = newNode
        } else {
            // 2. 中间
            let index = 0
            let current = this.head
            // 记录前一个节点
            let previous = null
            while (index < position) {
                // 依次往后找
                previous = current
                current = current.next
                index = index + 1
            }
            previous.next = newNode
            newNode.next = current
        }
        this.length++
        return true
    }
    // 获取对应位置的元素
    get(position) {
        // 0.判断越界问题
        if (position < 0 || position > this.length - 1) {
            return null
        }
        // 1.查找该位置的元素
        let index = 0
        let current = this.head
        while (index < position) {
            current = current.next
            index = index + 1
        }
        return current.element
    }
    // 返回元素索引
    indexOf(element) {
        // 先获取第一个元素
        let current = this.head
        let index = 0
        while (current) {
            if (current.element === element) {
                return index
            }
            index++
            current = current.next
        }
        // 如果找不到
        return -1
    }
    // 移除节点, 返回被删除的节点
    removeAt(position) {
        if (position < 0 || position > this.length - 1) {
            return null
        }
        let current = this.head
        let previous = null
        if (position === 0) {
            this.head = current.next
        } else {
            let index = 0
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = current.next
        }
        this.length--
        return current.element
    }
    // 更新节点
    update(position, element) {
        // 1.删除
        const result = this.removeAt(position)
        // 插入
        this.insert(position, element)
        // 返回更新前的节点
        return result
    }
    // 删除节点
    remove(element) {
        const index = this.indexOf(element)
        if (index === -1) {
            return
        }
        this.removeAt(index)
    }
    isEmpty() {
        return this.length === 0
    }
    size() {
        return this.length
    }
    // toString 可视化
    toString() {
        // 1.定义两个变量
        let current = this.head
        let listString = ""

        // 2.循环获取链表中所有的元素
        while (current) {
            listString += "->" + current.element
            current = current.next
        }

        // 3.返回最终结果
        return listString.slice(2)
    }
}